\subsection{Products}
We will use the symbol \( \lambda \) to define functions without giving them explicit names.
The syntax \( \lambda x.\, y \) represents the function \( f \) such that \( f(x) = y \).

Let \( \qty{\mathcal M_i}_{i \in I} \) be a set of \( \mathcal L \)-structures.
The \emph{product} \( \prod_{i \in I} \mathcal M_i \) of this family is the \( \mathcal L \)-structure with carrier set
\[ \prod_{i \in I} \mathcal M_i = \qty{\alpha : I \to \bigcup M_i \midd \alpha(i) \in \mathcal M_i} \]
such that
\begin{itemize}
    \item an \( n \)-ary function symbol \( f \) is interpreted as
    \[ f^{\prod_I \mathcal M_i} : \qty(\prod_I \mathcal M_i)^n \to \prod_I \mathcal M_i \]
    given by
    \[ (\alpha_1, \dots, \alpha_n) \mapsto \lambda i.\, f^{\mathcal M_i}(\alpha_1(i), \dots, \alpha_n(i)) \]
    \item an \( n \)-ary relation symbol \( R \) is interpreted as the subset
    \[ R^{\prod_I \mathcal M_i} \subseteq \qty(\prod_I \mathcal M_i)^n \]
    given by
    \[ R^{\prod_I \mathcal M_i} = \qty{(\alpha_1, \dots, \alpha_n) \in \qty(\prod_I \mathcal M_i)^n \midd \forall i \in I.\, (\alpha_1(i), \dots, \alpha_n(i)) \in R^{\mathcal M_i}} \]
\end{itemize}
The relation symbols in this kind of product are not particularly useful.
We want to construct a different kind of product in such a way that \( \varphi \) holds in the product if the set of \( \mathcal M_i \) that model \( \varphi \) is `large'.

\subsection{Lattices}
\begin{definition}
    A \emph{lattice} is a set \( L \) equipped with binary operations \( \wedge \) and \( \vee \) that are associative and commutative, and satisfy the \emph{absorption laws}
    \[ a \vee (a \wedge b) = a;\quad a \wedge (a \vee b) = a \]
    A lattice is called
    \begin{itemize}
        \item \emph{distributive}, if \( a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c) \);
        \item \emph{bounded}, if there are elements \( \bot \) and \( \top \) such that \( a \vee \bot = a \) and \( a \wedge \top = a \);
        \item \emph{complemented}, if it is bounded and for each \( a \in L \) there exists \( a^\star \in L \) called its \emph{complement} such that \( a \wedge a^\star = \bot \) and \( a \vee a^\star = \top \);
        \item a \emph{Boolean algebra}, if it is distributive, bounded, and complemented.
    \end{itemize}
\end{definition}
\begin{remark}
    \begin{enumerate}
        \item Distributive lattices model the fragment of a deduction system with only the conjunction and disjunction operators.
        Boolean algebras model classical propositional logic.
        \item Every lattice has an ordering, defined by \( a \leq b \) when \( a \wedge b = a \).
        This ordering models the provability relation between propositions.
    \end{enumerate}
\end{remark}
\begin{example}
    \begin{enumerate}
        \item Let \( I \) be a set.
        The power set \( \mathcal P(I) \) can be made into a Boolean algebra by taking \( \wedge = \cap \) and \( \vee = \cup \).
        \item More generally, let \( X \) be a topological space.
        The set of closed and open sets of \( X \) form a Boolean algebra; they can also be thought of as the propositions in classical logic.
        In fact, all Boolean algebras are of this form.
        This result is known as Stone's representation theorem.
        \item For any \( \mathcal L \)-structure \( \mathcal M \) and subset \( B \subseteq \mathcal M \), the set \( \qty{\varphi(\mathcal M) \mid \varphi(\vb x) \in \mathcal L_B} \) of definable subsets with parameters in \( B \) is a Boolean algebra.
    \end{enumerate}
\end{example}

\subsection{Filters}
\begin{definition}
    Let \( X \) be a lattice.
    A \emph{filter} \( \mathcal F \) on \( X \) is a subset of \( X \) such that
    \begin{enumerate}
        \item \( \mathcal F \neq \varnothing \);
        \item \( \mathcal F \) is \emph{upward closed}: if \( f \leq x \) and \( f \in \mathcal F \) then \( x \in \mathcal F \);
        \item \( \mathcal F \) is \emph{downward directed}: if \( x, y \in \mathcal F \), then \( x \wedge y \in \mathcal F \).
    \end{enumerate}
\end{definition}
For property (ii), we might also say that \( \mathcal F \) is a \emph{terminal segment} of \( X \).
% large things get "stuck in the filter"; filters measure largeness
\begin{example}
    \begin{enumerate}
        \item Given an element \( j \in I \), the family \( \mathcal F_j \) of all subsets of \( I \) containing \( j \) is a filter on \( \mathcal P(I) \).
        A filter of this form is called \emph{principal}.
        A filter that is not principal is called \emph{free}.
        \item The family of all cofinite subsets of \( I \) forms a filter on \( \mathcal P(I) \), called the \emph{Fr\'echet filter}.
        One can show that any free maximal filter on an infinite set must contain the Fr\'echet filter.
        % why?
        \item The family of measurable subsets of \( [0,1] \) with Lebesgue measure \( 1 \) is a filter.
    \end{enumerate}
\end{example}
\begin{definition}
    A filter \( \mathcal F \) on a lattice \( L \) is \emph{proper} if it is not equal to \( L \).
    A maximal proper filter is called an \emph{ultrafilter}.
\end{definition}
The ultrafilters on \( \mathcal P(I) \) are precisely those filters \( \mathcal F \) where for each \( U \subseteq I \), either \( U \in \mathcal F \) or \( I \setminus U \in \mathcal F \).
\begin{proposition}[the ultrafilter principle]
    Given a set \( I \), every proper filter on \( \mathcal P(I) \) can be extended to an ultrafilter.
\end{proposition}
The ultrafilter principle is a choice principle that is strictly weaker than the axiom of choice.
\begin{proof}
    Apply Zorn's lemma.
    % TODO: flesh out?
\end{proof}

\subsection{\L{}o\'s' theorem}
For \( \bm \alpha \in \prod_{i \in I} \mathcal M_i \) and \( \varphi(\vb x) \) an \( \mathcal L \)-formula, we write
\[ [\varphi(\bm \alpha)] = \qty{i \in I \mid \mathcal M_i \vDash \varphi(\bm \alpha(i))} \]
Let \( I \) be a set and \( \mathcal F \) be a filter on \( \mathcal P(I) \).
Let \( \qty{\mathcal M_i}_{i \in I} \) be a family of \( \mathcal L \)-structures.
The carrier set for the reduced product \( \faktor{\prod \mathcal M_i}{\mathcal F} \) is the quotient of the cartesian product \( \prod_{i \in I} \mathcal M_i \) by the equivalence relation defined by \( \alpha \sim \beta \) if and only if \( [\alpha = \beta] \in \mathcal F \).
We write \( \langle \alpha \rangle \) for the equivalence class of \( \alpha \) in the reduced product.
If \( \mathcal F \) is an ultrafilter, we call the reduced product an \emph{ultraproduct}.
If all of the factors \( \mathcal M_i \) are equal, the ultraproduct is called an \emph{ultrapower}.

We turn the reduced product into an \( \mathcal L \)-structure as follows.
\[ f^{\faktor{\prod \mathcal M_i}{\mathcal F}}(\langle \alpha_1 \rangle, \dots, \langle \alpha_n \rangle) = \langle \lambda i.\, f^{\mathcal M_i}(\alpha_1(i), \dots, \alpha_n(i)) \rangle \]
\[ (\langle \alpha_1 \rangle, \dots, \langle \alpha_n \rangle) \in R^{\faktor{\prod \mathcal M_i}{\mathcal F}} \iff [R(\alpha_1, \dots, \alpha_n)] \in \mathcal F \]
Note that if \( \mathcal F = \mathcal F_j \) is a principal filter, then \( \faktor{\prod \mathcal M_i}{\mathcal F} \cong \mathcal M_j \).

\begin{theorem}
    Let \( \qty{\mathcal M_i}_{i \in I} \) be a set of \( \mathcal L \)-structures, and \( \mathcal U \) be an ultrafilter on \( \mathcal P(I) \).
    Then for all \( (\langle \alpha_1 \rangle, \dots, \langle \alpha_n \rangle) \in \qty(\faktor{\prod \mathcal M_i}{\mathcal U})^n \) and \( \mathcal L \)-formulae \( \varphi(x_1, \dots, x_n) \),
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \varphi(\langle \alpha_1 \rangle, \dots, \langle \alpha_n \rangle) \iff [\varphi(\alpha_1, \dots, \alpha_n)] \in \mathcal U \]
\end{theorem}
In particular, if each \( \mathcal M_i \) is a model for some theory \( \mathcal T \), then so is the ultraproduct.
\begin{proof}
    We prove the result by induction on the length of \( \varphi \).
    The result holds for atomic formulae by the definition of the interpretations of function and relation symbols.
    Since all first-order formulae are equivalent to one composed of atomic formulae under negations, conjunctions, and existential quantification, it suffices to check these cases.

    If the theorem holds for \( \psi \), and \( \varphi = \neg \psi \), we can negate both sides of the induction hypothesis to show that
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \neg\psi \iff [\psi] \notin \mathcal U \]
    As \( \mathcal U \) is an ultrafilter, the right hand side holds if and only if the complement of \( [\psi] \) lies in \( \mathcal U \).
    But this complement is precisely \( [\neg\psi] \), as required.

    If the theorem holds for \( \psi_1, \psi_2 \), then
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \psi_i \iff [\psi_i] \in \mathcal U \]
    \begin{align*}
        \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \psi_1 \wedge \psi_2 &\iff [\psi_1] \in \mathcal U \text{ and } [\psi_2] \in \mathcal U \\
        &\iff [\psi_1 \wedge \psi_2] \in \mathcal U
    \end{align*}
    Indeed, if \( [\psi_1 \wedge \psi_2] \in \mathcal U \), then both \( [\psi_1] \) and \( [\psi_2] \) are in \( \mathcal U \), since \( [\psi_1 \wedge \psi_2] \subseteq [\psi_1], [\psi_2] \).
    Conversely, if \( [\psi_1], [\psi_2] \in \mathcal U \), then \( [\psi_1] \cap [\psi_2] \subseteq [\psi_1 \wedge \psi_2] \) as they are equal, but \( [\psi_1] \cap [\psi_2] \in \mathcal U \), so \( [\psi_1 \wedge \psi_2] \in \mathcal U \).

    For the case of existential quantification, we will use the axiom of choice.
    Let \( x \) be free in \( \psi \).
    We have
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \exists x.\, \psi(x) \iff \exists \langle \alpha \rangle.\, \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \psi(\langle \alpha \rangle) \]
    By the inductive hypothesis, the right hand side holds if and only if \( [\psi(\alpha)] \in \mathcal U \).
    Suppose that
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \psi(\langle \alpha \rangle) \]
    Then \( [\psi(\alpha)] \subseteq [\exists x.\, \psi(x)] \in \mathcal U \), as \( \mathcal U \) is a filter.

    Conversely, suppose \( [\exists x.\, \psi(x)] \in \mathcal U \).
    Using the axiom of choice, we can choose a witness \( \alpha(i) \) to \( \mathcal M_i \vDash \exists x.\, \psi(x) \) for each \( i \in [\exists x.\, \psi(x)] \).
    For each \( i \notin [\exists x.\, \psi(x)] \), we choose an arbitrary element of \( \mathcal M_i \).
    Hence,
    \[ \faktor{\prod \mathcal M_i}{\mathcal U} \vDash \psi(\langle \alpha \rangle) \]
\end{proof}
\begin{remark}
    \begin{enumerate}
        \item Since \( \mathcal U \) is an ultrafilter, the complement of \( [\exists x.\, \psi(x)] \) is not in \( \mathcal U \).
        Thus, the set of indices \( I \) for which \( \alpha(i) \) was chosen arbitrarily does not lie in the ultrafilter, so this choice does not change the equivalence class of \( \alpha \).
        \item The use of the axiom of choice in the above theorem is essential.
    \end{enumerate}
\end{remark}
\begin{example}
    We will show that the class of torsion groups is not first-order axiomatisable in the usual language of abelian groups with signature \( (+, 0) \).
    Let \( \mathcal U \) be a free ultrafilter on \( \omega \), and consider the ultraproduct
    \[ G = \faktor{\prod_{i < \omega} C_{i+1}}{\mathcal U} \]
    where \( C_i \) is the cyclic group of order \( i \), generated by \( g_i \).
    Consider the element
    \[ g = \langle \lambda i.\, g_i \rangle \in G \]
    This has finite order if and only if \( [ng = 0] \in \mathcal U \) for some \( n > 0 \).
    However, for each such \( n \), the set \( [ng = 0] \) is finite, so \( [ng \neq 0] \in \mathcal U \) as \( \mathcal U \) contains the Fr\'echet filter, thus \( [ng = 0] \notin \mathcal U \).
    But if the class of torsion groups were axiomatisable, this ultraproduct would also model that theory, and thus would be torsion.
\end{example}
\begin{example}
    Let \( \mathcal U \) be a free ultrafilter on \( \omega \), and consider the ultrapower
    \[ \mathbb N^{\mathcal U} = \faktor{\prod_{i < \omega} \mathbb N}{\mathcal U} \]
    Its elements are equivalence classes of sequences of natural numbers, where \( \langle(a_n)\rangle = \langle(b_n)\rangle \) if and only if \( \qty{n \mid a_n = b_n} \in \mathcal U \).
    It has elements such as \( \langle (n)_{n < \omega} \rangle \), which represent infinitely large numbers.
    If \( \mathbb N \) has its usual structure for the language of arithmetic \( \mathcal L_{\text{arith}} \), then the ultrapower \( \mathbb N^{\mathcal U} \) is a \emph{nonstandard model} of Peano arithmetic by \L{}o\'s' theorem, and is an elementary extension of \( \mathbb N \).
\end{example}
\begin{example}
    Let \( \mathcal U \) be a free ultrafilter on \( \omega \), and consider the ultrapower \( \mathbb R^{\mathcal U} \), which is an elementary extension of \( \mathbb R \).
    This includes `large numbers' bigger than any standard real number, such as \( \omega = \langle (n)_{n < \omega} \rangle \), and also includes `infinitesimal numbers' such as \( \frac{1}{\omega} \).
    This is not zero, but is smaller than any positive standard real.
\end{example}
We can give a semantic proof of the compactness theorem without using completeness, by using \L{}o\'s' theorem.
\begin{corollary}
    Let \( \mathcal T \) be a first-order theory such that every finite subset of \( \mathcal T \) has a model.
    Then \( \mathcal T \) has a model.
\end{corollary}
\begin{proof}
    If \( \mathcal T \) is finite, the result is trivial, so we may suppose it is infinite.
    Let \( I \) be the set of all finite subtheories of \( \mathcal T \).
    For each axiom \( \varphi \in \mathcal T \), define \( X_\varphi \) to be the set of finite subtheories of \( \mathcal T \) that include \( \varphi \) as an axiom, and let
    \[ D = \qty{Y \subseteq I \mid \exists \varphi \in \mathcal T.\, X_\varphi \subseteq Y} \]
    Then \( D \) is a proper filter on \( Y \), so by the ultrafilter principle, it can be extended to an ultrafilter \( \mathcal U \).
    Using the axiom of choice, let \( \mathcal M_\Delta \) be a model of \( \Delta \) for each finite subtheory \( \Delta \in I \).
    Then, for any \( \varphi \in \mathcal T \),
    \[ X_\varphi \subseteq \qty{\Delta \in I \mid M_\Delta \vDash \varphi} \]
    Thus \( \qty{\Delta \in I \mid M_\Delta \vDash \varphi} \in D \subseteq \mathcal U \).
    Then by \L{}o\'s' theorem, the ultraproduct \( \faktor{\prod_{\Delta \in I} \mathcal M_\Delta}{\mathcal U} \) models \( \varphi \).
    In particular, the ultraproduct models \( \mathcal T \).
\end{proof}
